from collections import deque
def change_num(s):
    for e in enumerate(s):
        for d in [-1,1]:
            index = e[0]
            y = str((int(e[1][index])+d)%10)
            yield  e[1][:index]+y+e[1][index+1:]


# def openLock(deadends,target):
#     init = {'0000'}
#     queue = deque([(init,0)])
#     dead = set({deadends})
#     while deque:
#         current_elem,depth = queue.popleft()
#         if current_elem == target:return depth
#         if current_elem == deadends:continue
#         for change_elem in change_num(current_elem):
#             if change_elem not in init:
#                 init.add(change_elem)
#                 queue.append((change_elem,depth+1))
#     return -1

def openLock(deadends, target):
    def neighbors(node):
        for i in range(4):
            x = int(node[i])
            for d in (-1, 1):
                y = (x + d) % 10
                yield node[:i] + str(y) + node[i + 1:]

    dead = set(deadends)
    queue = deque([('0000', 0)])
    seen = {'0000'}
    while queue:
        node, depth = queue.popleft()
        if node == target: return depth
        if node in dead: continue
        for nei in neighbors(node):
            if nei not in seen:
                seen.add(nei)
                queue.append((nei, depth + 1))
    return -1
def main():
    deadends = "8888"
    target = "0002"
    print(openLock(deadends,target))
if __name__ == "__main__":
    main()